package com.algorithm.贪心;

import java.util.Arrays;

/**
 * 在北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海
 * 有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值
 * 海盗船的载重量为 W，每件古董的重量为 𝑤i，海盗们该如何把尽可能多数量的古董装上海盗船?
 */
public class 海盗船装载问题 {
    public static void main(String[] args) {
        new 海盗船装载问题().pirate();
    }

    public void pirate() {
        int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
        int capacity = 30;
        int count = 0, weight = 0;
        Arrays.sort(weights);

        for (int i = 0; i < weights.length && weight < capacity; i++) {
            int newWeight = weights[i] + weight;
            if (newWeight <= capacity) {
                weight = newWeight;
                count++;
            }
        }
        System.out.println("一共装了" + count + "件宝贝，总重量为" + weight);
    }
}
